/*
Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".
*/

class Solution {
public:
    string addBinary(string a, string b) {
        string sum;
        alen = (int)a.length(); blen = (int)b.length();
        int mlen = max(alen, blen);
        int remainder = 0;
        for (int i = 0; i < mlen; i++) {
            const int ai = (i < alen)?(a[alen-i-1]-'0'):0;
            const int bi = (i < blen)?(b[blen-i-1]-'0'):0;
            const int val = (ai + bi + remainder)%2;
            remainder = (ai + bi + remainder)/2;
            sum += '0'+val;
        }
        if (remainder) sum += '1';
        reverse(sum.begin(), sum.end());
        return sum;
    }
private:
    int alen;
    int blen;
};

#if 0
class Solution {
public:
    string addBinary(string a, string b) {
        char c; string sum("");
        int m = a.length(), n = b.length(), remainder = 0;
        while(m && n) {
            if (a[m-1] == '1' && b[n-1] == '1') {
                c = (remainder)?'1':'0';
                remainder = 1;
            } else if (a[m-1] == '0' && b[n-1] == '0') {
                c = (remainder)?'1':'0';
                remainder = 0;
            } else { // '0' + '1'
                if (remainder) {c = '0'; remainder=1;}
                else {c = '1';}
            }
            sum += c; m--; n--;
        }
        // handling remaining characters
        while (m) {
            if (remainder) {
                c = (a[m-1] == '1')?'0':'1';
                remainder = (a[m-1] == '1')?1:0;
            } else {c = a[m-1];}
            sum += c; m--;
        }
        while (n) {
            if (remainder) {
                c = (b[n-1] == '1')?'0':'1';
                remainder = (b[n-1] == '1')?1:0;
            } else {c = b[n-1];}
            sum += c; n--;
        }
        if (remainder) sum += '1';
        reverse(sum.begin(), sum.end());
        return sum;
    }
};
#endif
